{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Reverse Bits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #divide-and-conquer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #分治"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: reverseBits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #颠倒二进制位"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>颠倒给定的 32 位无符号整数的二进制位。</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。</li>\n",
    "\t<li>在 Java 中，编译器使用<a href=\"https://baike.baidu.com/item/二进制补码/5295284\" target=\"_blank\">二进制补码</a>记法来表示有符号整数。因此，在 <strong>示例 2</strong>&nbsp;中，输入表示有符号整数 <code>-3</code>，输出表示有符号整数 <code>-1073741825</code>。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 00000010100101000001111010011100\n",
    "<strong>输出：</strong>964176192 (00111001011110000010100101000000)\n",
    "<strong>解释：</strong>输入的二进制串 <strong>00000010100101000001111010011100 </strong>表示无符号整数<strong> 43261596</strong><strong>，\n",
    "    </strong> 因此返回 964176192，其二进制表示形式为 <strong>00111001011110000010100101000000</strong>。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 11111111111111111111111111111101\n",
    "<strong>输出：</strong>3221225471 (10111111111111111111111111111111)\n",
    "<strong>解释：</strong>输入的二进制串 <strong>11111111111111111111111111111101</strong> 表示无符号整数 4294967293，\n",
    "   &nbsp; 因此返回 3221225471 其二进制表示形式为 <strong>10111111111111111111111111111111 。</strong></pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>输入是一个长度为 <code>32</code> 的二进制字符串</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶</strong>: 如果多次调用这个函数，你将如何优化你的算法？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [reverse-bits](https://leetcode.cn/problems/reverse-bits/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [reverse-bits](https://leetcode.cn/problems/reverse-bits/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['00000010100101000001111010011100', '11111111111111111111111111111101']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        cur = 0\n",
    "        cnt = 0\n",
    "        res = 0\n",
    "        for i in range(32):\n",
    "            if num&1:\n",
    "                cur += 1\n",
    "                cnt += 1\n",
    "            else:\n",
    "                cnt = cur + 1\n",
    "                cur = 0\n",
    "            num = num>>1\n",
    "            res = max(res, cnt)\n",
    "                \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        cur=0  # 当前位置为止连续1的个数\n",
    "        insert=0  # 在当前位置变成1，往前数连续1的最大个数\n",
    "        res=1  # 保存insert最大值即可\n",
    "        for i in range(32):\n",
    "            if num&(1<<i):\n",
    "                cur+=1\n",
    "                insert+=1\n",
    "            else:\n",
    "                insert=cur+1\n",
    "                cur=0\n",
    "            res=max(res,insert)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        if num >= 0:\n",
    "            bnum = bin(num)[2:]\n",
    "        else:\n",
    "            bnum = bin(num & 0xffffffff)[2:]\n",
    "        if len(bnum) < 32:\n",
    "            bnum = \"0\" + bnum\n",
    "        left_index = 0\n",
    "        right_index = 0\n",
    "        ans = 0\n",
    "        zero_indexes = list()\n",
    "        while right_index < len(bnum):\n",
    "            if bnum[right_index] == '0':\n",
    "                zero_indexes.append(right_index)\n",
    "            if len(zero_indexes) > 1:\n",
    "                ans = max(ans, right_index - left_index)\n",
    "                left_index = zero_indexes.pop(0) + 1\n",
    "            right_index += 1\n",
    "            if right_index == len(bnum):\n",
    "                ans = max(ans, right_index - left_index)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        # 思路: 目标长串中只能包含一个0 \n",
    "        # 从低位到高度遍历\n",
    "        #   遇到1, 则当前连续1长串长度 +1\n",
    "        #   遇到0, 则当前连续1长度长度 = 当前索引 - 上次遇到0的索引\n",
    "\n",
    "        #   8   4     \n",
    "        # 11011101111\n",
    "\n",
    "        cur = 0\n",
    "        rs = 0\n",
    "        last0 = -1  # 上次遇到0的位置\n",
    "        for i in range(32):\n",
    "            # 判断第i位是否为1\n",
    "            if num & (1 << i) != 0:\n",
    "                # 如果为1, 当前连续1的个数++\n",
    "                cur += 1\n",
    "            else:\n",
    "                rs = max(rs, cur)\n",
    "                # 如果为0\n",
    "                cur = i - last0\n",
    "                last0 = i\n",
    "        rs = max(rs, cur)\n",
    "        return rs\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        cur = 0\n",
    "        insert = 0\n",
    "        res = 1\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "               cur += 1\n",
    "               insert +=1\n",
    "            else:\n",
    "                insert = cur + 1\n",
    "                cur = 0\n",
    "            res = max(res,insert)\n",
    "        return res\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        # print(num)\n",
    "        # print(bin(num))\n",
    "        num=bin(num & 0xffffffff)[2:]\n",
    "        # print(num)\n",
    "\n",
    "        num=\"0\"*(32-len(num))+num\n",
    "        index=0\n",
    "        maxlen=0\n",
    "\n",
    "        while index<len(num):\n",
    "            nowlen=0\n",
    "\n",
    "            if num[index]==\"1\":\n",
    "                while index<len(num) and num[index]==\"1\":\n",
    "                    nowlen+=1\n",
    "                    index+=1\n",
    "\n",
    "                if index<len(num):\n",
    "                    last=index+1\n",
    "                    nowlen+=1\n",
    "                    index+=1\n",
    "                    while index<len(num) and num[index]==\"1\":\n",
    "                        nowlen+=1\n",
    "                        index+=1\n",
    "                    index=last\n",
    "\n",
    "            else:\n",
    "                nowlen+=1\n",
    "                index+=1\n",
    "                last=index\n",
    "                while index<len(num) and num[index]==\"1\":\n",
    "                    nowlen+=1\n",
    "                    index+=1\n",
    "                index=last\n",
    "\n",
    "            maxlen=max(maxlen,nowlen)\n",
    "            \n",
    "\n",
    "        return maxlen\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        length = 0\n",
    "        insert = 0\n",
    "        res = 1\n",
    "\n",
    "        for i in range(32):\n",
    "            if num & (1 << i):\n",
    "                length += 1\n",
    "                insert += 1\n",
    "            else:\n",
    "                insert = length + 1\n",
    "                length = 0\n",
    "            \n",
    "            res = max(res, insert)\n",
    "        \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        cur = 0\n",
    "        insert = 0\n",
    "        res = 1\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "               cur += 1\n",
    "               insert +=1\n",
    "            else:\n",
    "                insert = cur + 1\n",
    "                cur = 0\n",
    "            res = max(res,insert)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        if num < 0:\n",
    "            num += 2**32\n",
    "        bits = []\n",
    "        temp = num\n",
    "        while temp != 0:\n",
    "            bits.append(temp % 2)\n",
    "            temp //= 2\n",
    "        print(bin(num))\n",
    "        max1 = 1\n",
    "        prev1, current1, num0 = 0, 0, 0\n",
    "        for i in range(len(bits)):\n",
    "            if bits[i] == 1:\n",
    "                current1 += 1\n",
    "                temp_len = current1 + 1\n",
    "                if num0 <= 1:\n",
    "                    temp_len += prev1\n",
    "                max1 = max(max1, temp_len)\n",
    "            elif i > 0 and bits[i - 1] == 1:\n",
    "                num0 = 1\n",
    "                prev1 = current1\n",
    "                current1 = 0\n",
    "            else:\n",
    "                num0 += 1\n",
    "        return min(32, max1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        left = 0\n",
    "        counter = 0 \n",
    "        res = 0\n",
    "        for right in range(0 ,32): \n",
    "            counter += num >> right & 1 ^ 1\n",
    "            while counter > 1:\n",
    "                counter -= num >> left & 1 ^ 1\n",
    "                left += 1\n",
    "            res = max(right-left+1, res)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        # 思路: 目标长串中只能包含一个0 \n",
    "        # 从低位到高度遍历\n",
    "        #   遇到1, 则当前连续1长串长度 +1\n",
    "        #   遇到0, 则当前连续1长度长度 = 当前索引 - 上次遇到0的索引\n",
    "\n",
    "        #   8   4     \n",
    "        # 11011101111\n",
    "\n",
    "        cur = 0\n",
    "        rs = 0\n",
    "        last0 = -1  # 上次遇到0的位置\n",
    "        for i in range(32):\n",
    "            # 判断第i位是否为1\n",
    "            if num & (1 << i) != 0:\n",
    "                # 如果为1, 当前连续1的个数++\n",
    "                cur += 1\n",
    "            else:\n",
    "                # 如果为0\n",
    "                cur = i - last0\n",
    "                last0 = i\n",
    "            rs = max(rs, cur)\n",
    "        return rs\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        c=r=max1=0\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "                c+=1\n",
    "                r+=1\n",
    "            else:\n",
    "                r=c+1\n",
    "                c=0\n",
    "            max1=max(max1,r)\n",
    "        return max1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        if num<0:\n",
    "            num=int(num+math.pow(2,32))\n",
    "        w= list(bin(num)[2:])\n",
    "        t=[0]\n",
    "        for i in range(len(w)):\n",
    "            if  ascii('0')<= ascii(w[i])<=ascii('9'):\n",
    "                t.append(int(w[i]))\n",
    "        r=[0 for i in range(len(t))]\n",
    "        temp=[0 for i in range(len(t))]\n",
    "        temp[0]=1\n",
    "        r[0]=0\n",
    "        q=0\n",
    "        for i in range(1,len(t)):\n",
    "            if  t[i]==0:\n",
    "                j=i-1\n",
    "                while  True:\n",
    "                    if t[j]==0 or j==0:\n",
    "                        break\n",
    "                    j=j-1\n",
    "                temp[i]=i-j\n",
    "            else:\n",
    "                temp[i]=temp[i-1]+1\n",
    "            r[i]=max(temp[i],r[i-1])\n",
    "            if r[i]>q:\n",
    "                q=r[i]\n",
    "        if q>32:\n",
    "            q=32\n",
    "        return q\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        if num < 0:\n",
    "            num = 2**31 + 2**31 + num\n",
    "        if num == 0:\n",
    "            return 1\n",
    "        if num == 2**32 - 1:\n",
    "            return 32\n",
    "        bits = []\n",
    "        zeros = [0]\n",
    "        while True:\n",
    "            bits.append(num % 2)\n",
    "            if bits[-1] == 0:\n",
    "                zeros.append(len(bits))\n",
    "            num = num // 2\n",
    "            if num == 0:\n",
    "                break\n",
    "        zeros.append(len(bits)+1)\n",
    "\n",
    "        # print(bits)\n",
    "        if len(zeros) == 2:\n",
    "            return zeros[1] - zeros[0]\n",
    "        # print(zeros)\n",
    "        maxnum = zeros[2] - zeros[0] - 1\n",
    "        for i in range(len(zeros)-2):\n",
    "            maxnum = max(maxnum, zeros[i+2] - zeros[i] - 1)\n",
    "        return maxnum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        num = num&0Xffffffff\n",
    "        l = bin(num)[2:]\n",
    "        t = []\n",
    "        for c in l:\n",
    "            if len(t)==0:\n",
    "                t.append([c, 1])\n",
    "            else:\n",
    "                if t[-1][0] == c:\n",
    "                    t[-1][1] += 1\n",
    "                else:\n",
    "                    t.append([c, 1])\n",
    "        #print(t)\n",
    "\n",
    "        ret = 1\n",
    "        for i in range(len(t)):\n",
    "            if t[i][0] == '1':\n",
    "                ret = max(ret, t[i][1] + 1)\n",
    "            \n",
    "                if i<len(t)-2 and t[i+1][1] == 1:\n",
    "                    ret = max(ret, t[i][1] + t[i+2][1]+1)\n",
    "        return min(ret, 32)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def reverseBits(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        cur = 0\n",
    "        insert = 0\n",
    "        res = 1\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "               cur += 1\n",
    "               insert +=1\n",
    "            else:\n",
    "                insert = cur + 1\n",
    "                cur = 0\n",
    "            res = max(res,insert)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        cur=0\n",
    "        insert=0\n",
    "        res=1\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "                cur+=1\n",
    "                insert+=1\n",
    "            else:\n",
    "                insert=cur+1\n",
    "                cur=0\n",
    "            res=max(res,insert)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        dp = [0] * 2\n",
    "        res = 0\n",
    "        for i in range(32):\n",
    "            if num & (1 << i):\n",
    "                dp[0] += 1\n",
    "                dp[1] += 1\n",
    "            else:\n",
    "                dp[1] = dp[0] + 1\n",
    "                dp[0] = 0\n",
    "            res = max(res, *dp)\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        count = count1 =maxcount1 =0\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "                count+=1\n",
    "                count1+=1\n",
    "            else:\n",
    "                count1=count+1\n",
    "                count=0\n",
    "            maxcount1=max(maxcount1,count1)\n",
    "        return maxcount1\n",
    "            \n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        cur=0\n",
    "        insert=0\n",
    "        res=0\n",
    "        for i in range(32):\n",
    "            if num&(1<<i):\n",
    "                cur+=1\n",
    "                insert+=1\n",
    "            else:\n",
    "                insert=cur+1\n",
    "                cur=0\n",
    "            res=max(res,insert)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        num = num&0xffffffff\n",
    "        l = num.bit_length()\n",
    "\n",
    "        r = [0]\n",
    "\n",
    "        # print(l)\n",
    "        for i in range(1,l):\n",
    "            if not num&1:\n",
    "                r.append(i)\n",
    "            num = num>>1\n",
    "        r.append(l+1)\n",
    "\n",
    "        # print(r)\n",
    "\n",
    "        for i in range(len(r)-1, 0, -1):\n",
    "            r[i] = r[i]-r[i-1]-1\n",
    "\n",
    "        for i in range(len(r)-1):\n",
    "            r[i] += (r[i+1]+1)\n",
    "\n",
    "\n",
    "        # print(r)\n",
    "        return min(max(r), 32)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def reverseBits(self, num):\n",
    "        cur = 0\n",
    "        insert = 0\n",
    "        res = 1\n",
    "        for i in range(32):\n",
    "            if num & (1 << i):\n",
    "                cur += 1\n",
    "                insert += 1\n",
    "            else:\n",
    "                insert = cur + 1\n",
    "                cur = 0\n",
    "            res = max(res, insert)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def reverseBits(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        cur = 0\n",
    "        insert = 0\n",
    "        res = 1\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "               cur += 1\n",
    "               insert +=1\n",
    "            else:\n",
    "                insert = cur + 1\n",
    "                cur = 0\n",
    "            res = max(res,insert)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        if num==0 or num==1:return 1\n",
    "        val = []\n",
    "        tmp = 0\n",
    "        for i in range(32):\n",
    "            if (num>>i)&1==1:\n",
    "                if tmp>=0:\n",
    "                    tmp+=1\n",
    "                else:\n",
    "                    val.append(tmp)\n",
    "                    tmp=1\n",
    "            else:\n",
    "                if tmp>0:\n",
    "                    val.append(tmp)\n",
    "                    tmp = -1\n",
    "                else:\n",
    "                    tmp-=1\n",
    "        val.append(tmp)\n",
    "        sta = 1 if val[0]<0 else 0\n",
    "        res = val[sta]\n",
    "        n = len(val)\n",
    "        if n==1:return val[0]\n",
    "        for i in range(sta,n,2):\n",
    "            re=0\n",
    "            if i+2<n and val[i+1]==-1:\n",
    "                re += val[i+2]\n",
    "            re += val[i]+1\n",
    "            res = max(res,re)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        x = bin(num & 0xffffffff)[2:].split(\"0\")\n",
    "        n = len(x)\n",
    "        print(x)\n",
    "        if x:\n",
    "            res = len(x[0]) + 1\n",
    "        else:\n",
    "            res = 1\n",
    "        for i in range(n - 1):\n",
    "            res = max(res, len(x[i]) + len(x[i + 1]) + 1)\n",
    "        if res > 32:\n",
    "            return 32\n",
    "        return res\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        num = num&0xffffffff\n",
    "        \n",
    "        l = num.bit_length()\n",
    "\n",
    "        r = [0]\n",
    "\n",
    "        # print(l)\n",
    "        p = 0\n",
    "        for i in range(1,l):\n",
    "            if not num&1:\n",
    "                r.append(i-p-1)\n",
    "                p = i\n",
    "            num = num>>1\n",
    "        r.append(l-p)\n",
    "\n",
    "        # print(r)\n",
    "\n",
    "        # for i in range(len(r)-1, 0, -1):\n",
    "        #     r[i] = r[i]-r[i-1]-1\n",
    "\n",
    "        for i in range(len(r)-1):\n",
    "            r[i] += (r[i+1]+1)\n",
    "\n",
    "\n",
    "        # print(r)\n",
    "        return min(max(r), 32)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        cur=0 # 当前位置为止连续1的个数\n",
    "        insert=0 # 变1之后，当前位置为止连续1的个数\n",
    "        res=1\n",
    "        for i in range(32):\n",
    "            if num & (1<<i): # num的第i位为1\n",
    "                cur+=1\n",
    "                insert+=1\n",
    "            else: # num的第i位为0\n",
    "                insert=cur+1\n",
    "                cur=0\n",
    "            res=max(res,insert)\n",
    "        return res\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        if num < 0: # 处理负数\n",
    "            num = pow(2,32) - abs(num)\n",
    "        length = list(map(len,bin(num)[2:].ljust(32,'0').split('0'))) # 将num转为二进制，并以单个字符'0'分隔字符串,然后得出列表中每个字符串的长度,ljust用来前补'0'\n",
    "        return length[0] if len(length)==1 else max(length[i]+length[i+1] for i in range(len(length)-1))+1 # length长度为1说明32位二进制全为1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "\n",
    "        pre, cur = 0,0\n",
    "        res = 1\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "                cur += 1\n",
    "            else:\n",
    "                res = max(res, pre+cur)\n",
    "                pre = cur+1\n",
    "                cur = 0\n",
    "        res = max(res, pre+cur)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        cur, ins, ans = 0, 0, 0\n",
    "        \n",
    "        for i in range(32):\n",
    "            if num & (1<<i) != 0:\n",
    "                cur += 1\n",
    "                ins += 1\n",
    "            else:\n",
    "                ins = cur + 1\n",
    "                cur = 0\n",
    "            ans = max(ans, ins)\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        cur=0  # 当前位置为止连续1的个数\n",
    "        insert=0  # 在当前位置变成1，往前数连续1的最大个数\n",
    "        res=1  # 保存insert最大值即可\n",
    "        for i in range(32):\n",
    "            if num&(1<<i):\n",
    "                cur+=1\n",
    "                insert+=1\n",
    "            else:\n",
    "                insert=cur+1\n",
    "                cur=0\n",
    "            res=max(res,insert)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        count = count1 =maxcount1 =0\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "                count+=1\n",
    "                count1+=1\n",
    "            else:\n",
    "                count1=count+1\n",
    "                count=0\n",
    "            if maxcount1<count1:maxcount1=count1\n",
    "        return maxcount1\n",
    "            \n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        cur = 0\n",
    "        insert = 0\n",
    "        ans = 1\n",
    "        for i in range(32):\n",
    "            if num & 1 == 1:\n",
    "                cur += 1\n",
    "                insert += 1\n",
    "            else:\n",
    "                insert = cur + 1\n",
    "                cur = 0\n",
    "            num = num >> 1\n",
    "            ans = max(ans, insert)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        if num < 0:\n",
    "            num = 0xffffffff + num + 1\n",
    "        binstr = bin(num)[2:]\n",
    "        binstr = '0' * (32 - len(binstr)) + binstr\n",
    "        idx = [-1, ]\n",
    "        for i, num in enumerate(binstr):\n",
    "            if num == '0':\n",
    "                idx.append(i)\n",
    "        idx.append(len(binstr))\n",
    "        if len(idx) == 2:\n",
    "            return 32\n",
    "        res = 0\n",
    "        for i in range(2, len(idx)):\n",
    "            res = max(res, idx[i] - idx[i-2])\n",
    "        return res - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        if num < 0:\n",
    "            num = 2**32 + num\n",
    "        if num == 0:\n",
    "            return 1\n",
    "        if num == 2**32 - 1:\n",
    "            return 32\n",
    "        bits = []\n",
    "        zeros = [0]\n",
    "        while True:\n",
    "            bits.append(num % 2)\n",
    "            if bits[-1] == 0:\n",
    "                zeros.append(len(bits))\n",
    "            num = num // 2\n",
    "            if num == 0:\n",
    "                break\n",
    "        zeros.append(len(bits)+1)\n",
    "\n",
    "        # print(bits)\n",
    "        if len(zeros) == 2:\n",
    "            return zeros[1] - zeros[0]\n",
    "        # print(zeros)\n",
    "        maxnum = zeros[2] - zeros[0] - 1\n",
    "        for i in range(len(zeros)-2):\n",
    "            maxnum = max(maxnum, zeros[i+2] - zeros[i] - 1)\n",
    "        return maxnum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        res='{:032b}'.format(num)\n",
    "        if(num < 0):\n",
    "            num = num&0xFFFFFFFF\n",
    "            res = (bin(num))[2:]\n",
    "        print(res)\n",
    "        print(len(res))\n",
    "        dp=[]\n",
    "        temp=0\n",
    "        for x in res:\n",
    "            if x=='0':\n",
    "                dp.append(temp)\n",
    "                temp=0\n",
    "            elif x=='1':\n",
    "                temp+=1\n",
    "        dp.append(temp)\n",
    "        temp=0\n",
    "        print(dp)\n",
    "        if len(dp)==1:\n",
    "            return min(dp[0]+1,32)\n",
    "        for x in range(1,len(dp)):\n",
    "            temp=max(temp,dp[x-1]+dp[x]+1)\n",
    "        return min(32,temp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        if num == -1:\n",
    "            return 32\n",
    "        \n",
    "        a = 0\n",
    "        if num < 0:\n",
    "            a = num\n",
    "            num = -num\n",
    "\n",
    "        bnum = bin(num)[2:]\n",
    "        if a < 0:\n",
    "            while len(bnum) % 4 != 0:\n",
    "                bnum = '0' + bnum\n",
    "                \n",
    "            lb = []\n",
    "            for i in bnum:\n",
    "                if i == '1':\n",
    "                    lb.append('0')\n",
    "                else:\n",
    "                    lb.append('1')\n",
    "   \n",
    "            \n",
    "            rlb = lb[::-1]\n",
    "            rn = len(rlb)\n",
    "    \n",
    "            t = \"\"\n",
    "            for i in range(rn):\n",
    "             \n",
    "                if rlb[i] == '0':\n",
    "                    t += '1'\n",
    "                    t = t + \"\".join(rlb[i + 1:])\n",
    "                    break\n",
    "                else:\n",
    "                    t += '0'\n",
    "            bnum = t\n",
    "            bnum = '1' * (32 - len(bnum)) + bnum[::-1]\n",
    "\n",
    "        res = []\n",
    "        c1, c2 = 0, 0\n",
    "        for i in range(len(bnum)):\n",
    "            if bnum[i] == '0':\n",
    "                c1 += 1\n",
    "                res.append(i)\n",
    "            else:\n",
    "                c2 += 1\n",
    "\n",
    "        if c1 == 0:\n",
    "            return c2 + 1\n",
    "        elif c1 == 1:\n",
    "            return c2 + 1\n",
    "        elif c1 == 2:\n",
    "            return res[1]\n",
    "        else:\n",
    "            ans = res[1]\n",
    "            for j in range(2, len(res)):\n",
    "                ans = max(ans, res[j] - res[j - 2] - 1)\n",
    "            ans = max(ans, len(bnum) - res[-2] -1)\n",
    "            return min(32,ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        def count_bit(n:str):\n",
    "            max_n = 0\n",
    "            count = 0\n",
    "            for c in n:\n",
    "                if c == '1':\n",
    "                    count += 1\n",
    "                else:\n",
    "                    max_n = max(max_n, count)\n",
    "                    count = 0\n",
    "            max_n = max(max_n, count)\n",
    "            return max_n\n",
    "        \n",
    "        if num < 0:\n",
    "            for i in range(32):\n",
    "                num ^= 1 << i\n",
    "            num += 1\n",
    "\n",
    "        s = '0' + bin(num)[2:]\n",
    "        zero_pos = []\n",
    "        for i,c in enumerate(s):\n",
    "            if c == '0':\n",
    "                zero_pos.append(i)\n",
    "        \n",
    "        max_n = 0\n",
    "        for i in zero_pos:\n",
    "            max_n = max(max_n, count_bit(s[:i] + '1' + s[i+1:]))\n",
    "            \n",
    "        return max_n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        if num < 0:\n",
    "            num = 2**32 + num\n",
    "        if num == 0:\n",
    "            return 1\n",
    "        if num == 2**32 - 1:\n",
    "            return 32\n",
    "        bits = []\n",
    "        zeros = [0]\n",
    "        while True:\n",
    "            bits.append(num % 2)\n",
    "            if bits[-1] == 0:\n",
    "                zeros.append(len(bits))\n",
    "            num = num // 2\n",
    "            if num == 0:\n",
    "                break\n",
    "        zeros.append(len(bits)+1)\n",
    "\n",
    "        # print(bits)\n",
    "        if len(zeros) == 2:\n",
    "            return zeros[1] - zeros[0]\n",
    "        # print(zeros)\n",
    "        maxnum = 0\n",
    "        for i in range(len(zeros)-2):\n",
    "            maxnum = max(maxnum, zeros[i+2] - zeros[i] - 1)\n",
    "        return maxnum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def reverseBits(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        cur = 0\n",
    "        insert = 0\n",
    "        res = 1\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "               cur += 1\n",
    "               insert +=1\n",
    "            else:\n",
    "                insert = cur + 1\n",
    "                cur = 0\n",
    "            res = max(res,insert)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        cur, pre = 0, 0\n",
    "        ans = 1\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "                cur += 1\n",
    "            else:\n",
    "                ans = max(ans, cur + pre)\n",
    "                cur, pre = 0, cur + 1\n",
    "        ans = max(ans, cur + pre)\n",
    "        return ans\n",
    "\n",
    "        # pre, cur =0, 0\n",
    "        # res = 1\n",
    "        # for i in range(32):\n",
    "        #     if num & (1<<i):\n",
    "        #         cur+=1\n",
    "        #     else:\n",
    "        #         res=max(res, pre+cur)\n",
    "        #         pre = cur +1\n",
    "        #         cur = 0\n",
    "        # res=max(res, pre+cur)\n",
    "        # return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        c = 0\n",
    "        insert = 0\n",
    "        r = 1\n",
    "        for i in range(32):\n",
    "            if num &(1<<i):\n",
    "                c += 1\n",
    "                insert += 1\n",
    "            else:\n",
    "                insert = c + 1\n",
    "                c = 0\n",
    "            r = max(r,insert)\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def reverseBits(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        cur = 0\n",
    "        insert = 0\n",
    "        res = 1\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "               cur += 1\n",
    "               insert +=1\n",
    "            else:\n",
    "                insert = cur + 1\n",
    "                cur = 0\n",
    "            res = max(res,insert)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "\n",
    "        cur=0\n",
    "        insert=0\n",
    "        res=1\n",
    "\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "                cur+=1\n",
    "                insert+=1\n",
    "            else:\n",
    "                insert=cur+1\n",
    "                cur=0\n",
    "            res=max(res,insert)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        cur = 0\n",
    "        pre = 0\n",
    "        res = 0\n",
    "\n",
    "        for i in range(32):\n",
    "            if num & (1 << i):\n",
    "                cur += 1\n",
    "                pre += 1\n",
    "            else:\n",
    "                pre = cur + 1\n",
    "                cur = 0\n",
    "            res = max(res, pre)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        num_bin = self.getBin(num)\n",
    "        if 1 not in num_bin:\n",
    "            return 1\n",
    "        if 0 not in num_bin:\n",
    "            return len(num_bin)\n",
    "        # 思路：找出每个0的index记录下来，每次循环让一个0变成1，记录下当次变成0的最大长度，每次迭代更新\n",
    "        zero_index = []\n",
    "        for i in range(len(num_bin)):\n",
    "            if num_bin[i] == 0:\n",
    "                zero_index.append(i)\n",
    "        max_len = 0\n",
    "        for each in zero_index:\n",
    "            num_bin[each] = 1\n",
    "            temp_len = 0\n",
    "            if 0 not in num_bin:\n",
    "                return len(num_bin)\n",
    "            for i in range(len(num_bin)):\n",
    "                if num_bin[i] == 1:\n",
    "                    temp_len += 1\n",
    "                if num_bin[i] == 0 or (i == len(num_bin) - 1):\n",
    "                    max_len = max(max_len,temp_len)\n",
    "                    temp_len = 0\n",
    "            num_bin[each] = 0  # 这一步特别关键，一定要重新置为0\n",
    "        return max_len\n",
    "\n",
    "    def getBin(self,num):\n",
    "        \"\"\" 需要获得num的32为二进制码，注意负数应该是用补码来存放，正数的补码等于原码\n",
    "            相当于需要求num的32位补码\n",
    "            这里采用内置函数bin\n",
    "        \"\"\"\n",
    "        if num >= 0:\n",
    "            binary = bin(num)[2:]  # 对于正数，直接使用内置函数 bin 来获取二进制表示\n",
    "            binary = binary.zfill(32)  # 补足到32位\n",
    "        else:\n",
    "            binary = bin(2 ** 32 + num)[2:]  # 对于负数，先转换为补码形式，然后获取二进制表示\n",
    "        return [int(i) for i in binary]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def reverseBits(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        cur = 0\n",
    "        insert = 0\n",
    "        res = 1\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "               cur += 1\n",
    "               insert +=1\n",
    "            else:\n",
    "                insert = cur + 1\n",
    "                cur = 0\n",
    "            res = max(res,insert)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        ans = pre = cur = 0\n",
    "        for i in range(32):\n",
    "            if num & (1 << i):\n",
    "                cur += 1\n",
    "            else:\n",
    "                ans = max(ans, pre + cur)\n",
    "                pre = cur + 1\n",
    "                cur = 0\n",
    "        ans = max(ans, pre + cur)\n",
    "        return ans\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        curr = 0\n",
    "        insert = 0\n",
    "        res = 1\n",
    "        for i in range(32):\n",
    "            if num & (1 << i):\n",
    "                curr += 1\n",
    "                insert += 1\n",
    "            else:\n",
    "                insert = curr + 1\n",
    "                curr = 0\n",
    "            res = max(res, insert)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        num_bin = self.getBin(num)\n",
    "        if 1 not in num_bin:\n",
    "            return 1\n",
    "        if 0 not in num_bin:\n",
    "            return len(num_bin)\n",
    "        # 思路：找出每个0的index记录下来，每次循环让一个0变成1，记录下当次变成0的最大长度，每次迭代更新\n",
    "        zero_index = []\n",
    "        for i in range(len(num_bin)):\n",
    "            if num_bin[i] == 0:\n",
    "                zero_index.append(i)\n",
    "        max_len = 0\n",
    "        for each in zero_index:\n",
    "            num_bin[each] = 1\n",
    "            temp_len = 0\n",
    "            if 0 not in num_bin:\n",
    "                return len(num_bin)\n",
    "            for i in range(len(num_bin)):\n",
    "                if num_bin[i] == 1:\n",
    "                    temp_len += 1\n",
    "                if num_bin[i] == 0 or (i == len(num_bin) - 1):\n",
    "                    max_len = max(max_len,temp_len)\n",
    "                    temp_len = 0\n",
    "            num_bin[each] = 0  # 这一步特别关键，一定要重新置为0\n",
    "        return max_len\n",
    "\n",
    "    def getBin(self,num):\n",
    "        \"\"\" 需要获得num的32为二进制码，注意负数应该是用补码来存放，正数的补码等于原码\n",
    "            相当于需要求num的32位补码\n",
    "            这里采用内置函数bin\n",
    "        \"\"\"\n",
    "        if num >= 0:\n",
    "            binary = bin(num)[2:]  # 对于正数，直接使用内置函数 bin 来获取二进制表示\n",
    "            binary = binary.zfill(32)  # 补足到32位\n",
    "        else:\n",
    "            binary = bin(2 ** 32 + num)[2:]  # 对于负数，先转换为补码形式，然后获取二进制表示\n",
    "        return [int(i) for i in binary]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def reverseBits(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        cur = 0\n",
    "        insert = 0\n",
    "        res = 1\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "               cur += 1\n",
    "               insert +=1\n",
    "            else:\n",
    "                insert = cur + 1\n",
    "                cur = 0\n",
    "            res = max(res,insert)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        left = 0\n",
    "        counter = 0 \n",
    "        res = 0\n",
    "        for right in range(0 ,32): \n",
    "            counter += num >> right & 1 ^ 1\n",
    "            while counter > 1:\n",
    "                counter -= num >> left & 1 ^ 1\n",
    "                left += 1\n",
    "            res = max(right-left+1, res)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        if num==0 or num==1:return 1\n",
    "        val = []\n",
    "        tmp = 0\n",
    "        for i in range(32):\n",
    "            if (num>>i)&1==1:\n",
    "                if tmp>=0:\n",
    "                    tmp+=1\n",
    "                else:\n",
    "                    val.append(tmp)\n",
    "                    tmp=1\n",
    "            else:\n",
    "                if tmp>0:\n",
    "                    val.append(tmp)\n",
    "                    tmp = -1\n",
    "                else:\n",
    "                    tmp-=1\n",
    "        val.append(tmp)\n",
    "        sta = 1 if val[0]<0 else 0\n",
    "        res = val[sta]\n",
    "        n = len(val)\n",
    "        if n==1:return val[0]\n",
    "        for i in range(sta,n,2):\n",
    "            re=0\n",
    "            if i+2<n and val[i+1]==-1:\n",
    "                re += val[i+2]\n",
    "            re += val[i]+1\n",
    "            res = max(res,re)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        left = 0\n",
    "        counter = 0 \n",
    "        res = 0\n",
    "        for right in range(0 ,32): \n",
    "            counter += num >> right & 1 ^ 1\n",
    "            while counter > 1:\n",
    "                counter -= num >> left & 1 ^ 1\n",
    "                left += 1\n",
    "            res = max(right-left+1, res)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def reverseBits(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        cur = 0\n",
    "        insert = 0\n",
    "        res = 1\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "               cur += 1\n",
    "               insert +=1\n",
    "            else:\n",
    "                insert = cur + 1\n",
    "                cur = 0\n",
    "            res = max(res,insert)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        if num < 0:\n",
    "            num = abs(num)\n",
    "            for i in range(32, -1, -1):\n",
    "                if num >> i & 1 == 0:\n",
    "                    num |= 1 << i\n",
    "                else: num ^= 1 << i\n",
    "            num += 1\n",
    "        left = [0] * 32\n",
    "        right = [0] * 32\n",
    "        for i in range(32):\n",
    "            if num >> i & 1: left[i] += left[i - 1] + 1\n",
    "            else: left[i] = 0\n",
    "        for i in range(31, -1, -1):\n",
    "            if num >> i & 1: right[i] += right[(i + 1) % 32] + 1\n",
    "            else: right[i] = 0\n",
    "        res = 0\n",
    "        for i in range(32):\n",
    "            if num >> i & 1 == 0:\n",
    "                a = 0 if i - 1 < 0 else left[i - 1]\n",
    "                b = 0 if i + 1 == 32 else right[i + 1]\n",
    "                res = max(res, a + b + 1)\n",
    "        return max(res, max(left), max(right))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        # 需要注意这里是补码\n",
    "        if num<0:\n",
    "            num = bin(num & 0xffffffff)[2:]\n",
    "        else:\n",
    "            num = bin(num)[2:]\n",
    "            num = '0'*(32-len(num))+num\n",
    "        num = [int(i) for i in num]\n",
    "        @cache\n",
    "        def dp(i, k):\n",
    "            if k<0:\n",
    "                return 0\n",
    "            if i==0:\n",
    "                return int(k==1 or num[0]==1)\n",
    "            if num[i]==1:\n",
    "                return dp(i-1, k)+1\n",
    "            else:\n",
    "                return dp(i-1, k-1)+k\n",
    "        res = 0\n",
    "        for i in range(len(num)):\n",
    "            res = max(res, dp(i, 1))\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        if num == -1:\n",
    "            return 32\n",
    "        num_bin = self.getBin(num)\n",
    "        # 思路 对二进制列表进行分割，分隔符为0\n",
    "        # 对剩余多个1的数组，只需考虑连续的两个和最大，并加一即是最后结果\n",
    "        num_spl = num_bin.split(\"0\")\n",
    "        max_len = 0\n",
    "        for i in range(len(num_spl) - 1):\n",
    "                max_len = max(max_len,len(num_spl[i])+len(num_spl[i+1]))\n",
    "        return max_len + 1\n",
    "\n",
    "\n",
    "    def getBin(self,num):\n",
    "        \"\"\" 需要获得num的32为二进制码，注意负数应该是用补码来存放，正数的补码等于原码\n",
    "            相当于需要求num的32位补码\n",
    "            这里采用内置函数bin\n",
    "\n",
    "            注意为什么这里需要用32位呢，因为需要考虑负数\n",
    "        \"\"\"\n",
    "        if num >= 0:\n",
    "            binary = bin(num)[2:]  # 对于正数，直接使用内置函数 bin 来获取二进制表示\n",
    "            binary = binary.zfill(32)  # 补足到32位\n",
    "        else:\n",
    "            binary = bin(2 ** 32 + num)[2:]  # 对于负数，先转换为补码形式，然后获取二进制表示\n",
    "        return binary"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        # cur, pre = 0, 0\n",
    "        # ans = 0\n",
    "        # while num:\n",
    "        #     if num % 2 == 0:\n",
    "        #         ans = max(ans, cur + pre + 1)\n",
    "        #         cur, pre = 0, cur\n",
    "        #     else:\n",
    "        #         cur += 1\n",
    "        #     num = num >> 1\n",
    "        # ans = max(ans, cur + pre + 1)\n",
    "        # return ans\n",
    "        pre, cur =0, 0\n",
    "        res = 1\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "                cur+=1\n",
    "            else:\n",
    "                res=max(res, pre+cur)\n",
    "                pre = cur +1\n",
    "                cur = 0\n",
    "        res=max(res, pre+cur)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        res = []\n",
    "        i = 32\n",
    "        while i:\n",
    "            temp = num & 1\n",
    "            res.append(temp)\n",
    "            num = num >> 1\n",
    "            i -= 1\n",
    "        cnt = 0\n",
    "        q = []\n",
    "        max_length = 0\n",
    "        for i in res:\n",
    "            if i == 1:\n",
    "                q.append(i)\n",
    "            else:\n",
    "                if cnt == 0:\n",
    "                    q.append(i)\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    max_length = max(max_length, len(q))\n",
    "                    cnt -= 1\n",
    "                    while True:\n",
    "                        temp = q.pop(0)\n",
    "                        if temp == 0:\n",
    "                            break\n",
    "                    q.append(i)\n",
    "                    cnt += 1\n",
    "        if max_length == 0:\n",
    "            max_length = len(q)\n",
    "        else:\n",
    "            if cnt == 1 and res[-1] == 1:\n",
    "                max_length = max(max_length, len(q))\n",
    "            else:\n",
    "                max_length = max(max_length, len(q))\n",
    "        return max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        res = []\n",
    "        i = 32\n",
    "        while i:\n",
    "            temp = num & 1\n",
    "            res.append(temp)\n",
    "            num = num >> 1\n",
    "            i -= 1\n",
    "        cnt = 0\n",
    "        q = []\n",
    "        max_length = 0\n",
    "        for i in res:\n",
    "            if i == 1:\n",
    "                q.append(i)\n",
    "            else:\n",
    "                if cnt == 0:\n",
    "                    q.append(i)\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    max_length = max(max_length, len(q))\n",
    "                    cnt -= 1\n",
    "                    while True:\n",
    "                        temp = q.pop(0)\n",
    "                        if temp == 0:\n",
    "                            break\n",
    "                    q.append(i)\n",
    "                    cnt += 1\n",
    "        max_length = max(max_length, len(q))\n",
    "        return max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        num_bin = self.getBin(num)\n",
    "        if 1 not in num_bin:\n",
    "            return 1\n",
    "        if 0 not in num_bin:\n",
    "            return len(num_bin)\n",
    "        # 思路：找出每个0的index记录下来，每次循环让一个0变成1，记录下当次变成0的最大长度，每次迭代更新\n",
    "        zero_index = []\n",
    "        for i in range(len(num_bin)):\n",
    "            if num_bin[i] == 0:\n",
    "                zero_index.append(i)\n",
    "        max_len = 0\n",
    "        for each in zero_index:\n",
    "            num_bin[each] = 1\n",
    "            temp_len = 0\n",
    "            if 0 not in num_bin:\n",
    "                return len(num_bin)\n",
    "            for i in range(len(num_bin)):\n",
    "                if num_bin[i] == 1:\n",
    "                    temp_len += 1\n",
    "                if num_bin[i] == 0 or (i == len(num_bin) - 1):\n",
    "                    max_len = max(max_len,temp_len)\n",
    "                    temp_len = 0\n",
    "            num_bin[each] = 0  # 这一步特别关键，一定要重新置为0\n",
    "        return max_len\n",
    "\n",
    "    def getBin(self,num):\n",
    "        \"\"\" 需要获得num的32为二进制码，注意负数应该是用补码来存放，正数的补码等于原码\n",
    "            相当于需要求num的32位补码\n",
    "            这里采用内置函数bin\n",
    "        \"\"\"\n",
    "        if num >= 0:\n",
    "            binary = bin(num)[2:]  # 对于正数，直接使用内置函数 bin 来获取二进制表示\n",
    "            binary = binary.zfill(32)  # 补足到32位\n",
    "        else:\n",
    "            binary = bin(2 ** 32 + num)[2:]  # 对于负数，先转换为补码形式，然后获取二进制表示\n",
    "        return [int(i) for i in binary]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        if num == -1:\n",
    "            return 32\n",
    "        \n",
    "        a = 0\n",
    "        if num < 0:\n",
    "            a = num\n",
    "            num = -num\n",
    "\n",
    "        bnum = bin(num)[2:]\n",
    "        if a < 0:\n",
    "            while len(bnum) % 4 != 0:\n",
    "                bnum = '0' + bnum\n",
    "                \n",
    "            lb = []\n",
    "            for i in bnum:\n",
    "                if i == '1':\n",
    "                    lb.append('0')\n",
    "                else:\n",
    "                    lb.append('1')\n",
    "   \n",
    "            \n",
    "            rlb = lb[::-1]\n",
    "            rn = len(rlb)\n",
    "    \n",
    "            t = \"\"\n",
    "            for i in range(rn):\n",
    "             \n",
    "                if rlb[i] == '0':\n",
    "                    t += '1'\n",
    "                    t = t + \"\".join(rlb[i + 1:])\n",
    "                    break\n",
    "                else:\n",
    "                    t += '0'\n",
    "            bnum = t\n",
    "            bnum = '1' * (32 - len(bnum)) + bnum[::-1]\n",
    "\n",
    "        res = []\n",
    "        c1, c2 = 0, 0\n",
    "        for i in range(len(bnum)):\n",
    "            if bnum[i] == '0':\n",
    "                c1 += 1\n",
    "                res.append(i)\n",
    "            else:\n",
    "                c2 += 1\n",
    "\n",
    "        if c1 == 0:\n",
    "            return c2 + 1\n",
    "        elif c1 == 1:\n",
    "            return c2 + 1\n",
    "        elif c1 == 2:\n",
    "            return res[1]\n",
    "        else:\n",
    "            ans = res[1]\n",
    "            for j in range(2, len(res)):\n",
    "                ans = max(ans, res[j] - res[j - 2] - 1)\n",
    "            ans = max(ans, len(bnum) - res[-2] -1)\n",
    "            return min(32,ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        res = []\n",
    "        i = 32\n",
    "        while i:\n",
    "            temp = num & 1\n",
    "            res.append(temp)\n",
    "            num = num >> 1\n",
    "            i -= 1\n",
    "        cnt = 0\n",
    "        q = []\n",
    "        max_length = 0\n",
    "        for i in res:\n",
    "            if i == 1:\n",
    "                q.append(i)\n",
    "            else:\n",
    "                if cnt == 0:\n",
    "                    q.append(i)\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    max_length = max(max_length, len(q))\n",
    "                    cnt -= 1\n",
    "                    while True:\n",
    "                        temp = q.pop(0)\n",
    "                        if temp == 0:\n",
    "                            break\n",
    "                    q.append(i)\n",
    "                    cnt += 1\n",
    "        if max_length == 0:\n",
    "            max_length = len(q)\n",
    "        else:\n",
    "            max_length = max(max_length, len(q))\n",
    "        return max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        cur = 0\n",
    "        insert = 0\n",
    "        res = 1\n",
    "        for _ in range(32):\n",
    "            if num & 1 == 1:\n",
    "                cur += 1\n",
    "                insert += 1\n",
    "            else:\n",
    "                insert = cur + 1\n",
    "                cur = 0\n",
    "            res = max(res, insert)\n",
    "            num >>= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "      \n",
    "        cur = 0\n",
    "        insert = 0\n",
    "        res = 1\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "               cur += 1\n",
    "               insert +=1\n",
    "            else:\n",
    "                insert = cur + 1\n",
    "                cur = 0\n",
    "            res = max(res,insert)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "      \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        num_bin = self.getBin(num)\n",
    "        if 1 not in num_bin:\n",
    "            return 1\n",
    "        if 0 not in num_bin:\n",
    "            return len(num_bin)\n",
    "        # 思路：找出每个0的index记录下来，每次循环让一个0变成1，记录下当次变成0的最大长度，每次迭代更新\n",
    "        zero_index = []\n",
    "        for i in range(len(num_bin)):\n",
    "            if num_bin[i] == 0:\n",
    "                zero_index.append(i)\n",
    "        max_len = 0\n",
    "        for each in zero_index:\n",
    "            num_bin[each] = 1\n",
    "            temp_len = 0\n",
    "            if 0 not in num_bin:\n",
    "                return len(num_bin)\n",
    "            for i in range(len(num_bin)):\n",
    "                if num_bin[i] == 1:\n",
    "                    temp_len += 1\n",
    "                if num_bin[i] == 0 or (i == len(num_bin) - 1):\n",
    "                    max_len = max(max_len,temp_len)\n",
    "                    temp_len = 0\n",
    "            num_bin[each] = 0  # 这一步特别关键，一定要重新置为0\n",
    "        return max_len\n",
    "\n",
    "    def getBin(self,num):\n",
    "        \"\"\" 需要获得num的32为二进制码，注意负数应该是用补码来存放，正数的补码等于原码\n",
    "            相当于需要求num的32位补码\n",
    "            这里采用内置函数bin\n",
    "        \"\"\"\n",
    "        if num >= 0:\n",
    "            binary = bin(num)[2:]  # 对于正数，直接使用内置函数 bin 来获取二进制表示\n",
    "            binary = binary.zfill(32)  # 补足到32位\n",
    "        else:\n",
    "            binary = bin(2 ** 32 + num)[2:]  # 对于负数，先转换为补码形式，然后获取二进制表示\n",
    "        return [int(i) for i in binary]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        if num == 0:\n",
    "            return 1\n",
    "        m = 0\n",
    "        s = '0' + bin(num)[2:] if num > 0 else bin(num & 0xffffffff)[2:]\n",
    "        dp = [0] * len(s)\n",
    "\n",
    "        def dfs(dp: List, index: int, s: str, c: bool):\n",
    "            nonlocal m\n",
    "            if index == len(s):\n",
    "                return\n",
    "            if s[index] == '1':\n",
    "                dp[index] = dp[index - 1] + 1 if index > 0 else 1\n",
    "                m = max(m, dp[index])\n",
    "                dfs(dp, index + 1, s, c)\n",
    "            else:\n",
    "                if not c:\n",
    "                    dp[index] = 0\n",
    "                    dfs(dp, index + 1, s, c)\n",
    "                else:\n",
    "                    dp[index] = 0\n",
    "                    dfs(dp, index + 1, s, True)\n",
    "                    # 这个策略影响的是之后的dp值，所以删去\n",
    "                    for i in range(index + 1, len(dp)):\n",
    "                        dp[i] = 0\n",
    "                    temp = s[:index] + '1' + s[index + 1:]\n",
    "                    dp[index] = dp[index - 1] + 1 if index > 0 else 1\n",
    "                    m = max(m, dp[index])\n",
    "                    dfs(dp, index + 1, temp, False)\n",
    "                    for i in range(index + 1, len(dp)):\n",
    "                        dp[i] = 0\n",
    "\n",
    "        dfs(dp, 0, s, True)\n",
    "        return m\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, n: int) -> int:\n",
    "        j = 0\n",
    "        for i in range(32):\n",
    "            j = j<<1\n",
    "            j += int(str(n%2))\n",
    "            n = n>>1\n",
    "        return j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, n: int) -> int:\n",
    "\n",
    "        ans = 0\n",
    "        t = 1<<31\n",
    "        while n:\n",
    "            ans += (n%2) * t\n",
    "            n >>= 1\n",
    "            t >>= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, n: int) -> int:\n",
    "\n",
    "        ans = 0\n",
    "        t = 1<<31\n",
    "        while n:\n",
    "            ans += (n%2) * t\n",
    "            n >>= 1\n",
    "            t >>= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, n: int) -> int:\n",
    "        bin_str = bin(n)[2:]\n",
    "        bin_str = bin_str.zfill(32)[::-1]\n",
    "        return int(bin_str, base=2)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def reverseBits(self, n: int) -> int:\r\n",
    "        result = 0\r\n",
    "        for i in range(32):\r\n",
    "            bit = n & 1\r\n",
    "            n = n >> 1\r\n",
    "            result = result << 1 | bit\r\n",
    "        return result\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, n: int) -> int:\n",
    "\n",
    "        res = n & 1\n",
    "\n",
    "        for i in range(31):\n",
    "            res = res << 1\n",
    "            n = n >> 1\n",
    "            res += n & 1\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, n: int) -> int:\n",
    "        recorder = 0\n",
    "        count = 31\n",
    "        while n:\n",
    "            recorder |= (n&1) << count\n",
    "            count -= 1\n",
    "            n >>= 1\n",
    "        return recorder\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, n: int) -> int:\n",
    "        res=0\n",
    "        power=31\n",
    "        while n:\n",
    "            res+=(n&1)<<power   #安排翻转之后第power位的数字 为啥不是32呢起始\n",
    "            n=n>>1\n",
    "            power-=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, n: int) -> int:\n",
    "        ret = 0\n",
    "        for i in range(32):\n",
    "            ret <<= 1\n",
    "            ret |= (n&1)\n",
    "            n >>= 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, n: int) -> int:\n",
    "        return int(\"0b\"+bin(n)[2:].zfill(32)[::-1],2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def reverseBits(self, n: int) -> int:\r\n",
    "        res = 0\r\n",
    "        for i in range(32):\r\n",
    "            res <<= 1\r\n",
    "            res += n & 1\r\n",
    "            n >>= 1\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, n: int) -> int:\n",
    "        return int(bin(n)[2:].rjust(32, '0')[::-1], 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, n: int) -> int:\n",
    "        n = (n >> 16) | (n << 16);\n",
    "        n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8);\n",
    "        n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4);\n",
    "        n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2);\n",
    "        n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1);\n",
    "        return n;\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, n: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(32):\n",
    "            res <<= 1\n",
    "            res |= n & 1\n",
    "            n >>= 1\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, n: int) -> int:\n",
    "        # ans=0\n",
    "        # dct={}\n",
    "        # n=str(n)\n",
    "        # for i,j in enumerate(n):\n",
    "        #     j=int(j)\n",
    "        #     for k in range(i):\n",
    "        #         j*=2\n",
    "        #     ans+=j\n",
    "        # # print(dct)\n",
    "        # return ans\n",
    "        print(bin(n))\n",
    "        n=bin(n)[2:]\n",
    "        if len(n)<32:\n",
    "            for i in range(32-len(n)):\n",
    "                n='0'+n\n",
    "        print(n)\n",
    "        # n=str(n)\n",
    "        def sum(lens,n):\n",
    "            if lens==1:\n",
    "                return int(n[lens-1])*(2**(lens-1))\n",
    "                # print(int(n[lens-1])*(2**(lens-1)))\n",
    "            return int(n[lens-1])*(2**(lens-1))+sum(lens-1,n)\n",
    "        return sum(len(n),n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, n: int) -> int:\n",
    "        bitmap = {0: 0, 1: 128, 2: 64, 3: 192, 4: 32, 5: 160, 6: 96, 7: 224, 8: 16, 9: 144, 10: 80, 11: 208, 12: 48, 13: 176, 14: 112, 15: 240, 16: 8, 17: 136, 18: 72, 19: 200, 20: 40, 21: 168, 22: 104, 23: 232, 24: 24, 25: 152, 26: 88, 27: 216, 28: 56, 29: 184, 30: 120, 31: 248, 32: 4, 33: 132, 34: 68, 35: 196, 36: 36, 37: 164, 38: 100, 39: 228, 40: 20, 41: 148, 42: 84, 43: 212, 44: 52, 45: 180, 46: 116, 47: 244, 48: 12, 49: 140, 50: 76, 51: 204, 52: 44, 53: 172, 54: 108, 55: 236, 56: 28, 57: 156, 58: 92, 59: 220, 60: 60, 61: 188, 62: 124, 63: 252, 64: 2, 65: 130, 66: 66, 67: 194, 68: 34, 69: 162, 70: 98, 71: 226, 72: 18, 73: 146, 74: 82, 75: 210, 76: 50, 77: 178, 78: 114, 79: 242, 80: 10, 81: 138, 82: 74, 83: 202, 84: 42, 85: 170, 86: 106, 87: 234, 88: 26, 89: 154, 90: 90, 91: 218, 92: 58, 93: 186, 94: 122, 95: 250, 96: 6, 97: 134, 98: 70, 99: 198, 100: 38, 101: 166, 102: 102, 103: 230, 104: 22, 105: 150, 106: 86, 107: 214, 108: 54, 109: 182, 110: 118, 111: 246, 112: 14, 113: 142, 114: 78, 115: 206, 116: 46, 117: 174, 118: 110, 119: 238, 120: 30, 121: 158, 122: 94, 123: 222, 124: 62, 125: 190, 126: 126, 127: 254, 128: 1, 129: 129, 130: 65, 131: 193, 132: 33, 133: 161, 134: 97, 135: 225, 136: 17, 137: 145, 138: 81, 139: 209, 140: 49, 141: 177, 142: 113, 143: 241, 144: 9, 145: 137, 146: 73, 147: 201, 148: 41, 149: 169, 150: 105, 151: 233, 152: 25, 153: 153, 154: 89, 155: 217, 156: 57, 157: 185, 158: 121, 159: 249, 160: 5, 161: 133, 162: 69, 163: 197, 164: 37, 165: 165, 166: 101, 167: 229, 168: 21, 169: 149, 170: 85, 171: 213, 172: 53, 173: 181, 174: 117, 175: 245, 176: 13, 177: 141, 178: 77, 179: 205, 180: 45, 181: 173, 182: 109, 183: 237, 184: 29, 185: 157, 186: 93, 187: 221, 188: 61, 189: 189, 190: 125, 191: 253, 192: 3, 193: 131, 194: 67, 195: 195, 196: 35, 197: 163, 198: 99, 199: 227, 200: 19, 201: 147, 202: 83, 203: 211, 204: 51, 205: 179, 206: 115, 207: 243, 208: 11, 209: 139, 210: 75, 211: 203, 212: 43, 213: 171, 214: 107, 215: 235, 216: 27, 217: 155, 218: 91, 219: 219, 220: 59, 221: 187, 222: 123, 223: 251, 224: 7, 225: 135, 226: 71, 227: 199, 228: 39, 229: 167, 230: 103, 231: 231, 232: 23, 233: 151, 234: 87, 235: 215, 236: 55, 237: 183, 238: 119, 239: 247, 240: 15, 241: 143, 242: 79, 243: 207, 244: 47, 245: 175, 246: 111, 247: 239, 248: 31, 249: 159, 250: 95, 251: 223, 252: 63, 253: 191, 254: 127, 255: 255}\n",
    "        result = 0\n",
    "        for i in range(4):\n",
    "            result <<= 8\n",
    "            result |= bitmap[n & 255]\n",
    "            n >>= 8\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, n: int) -> int:\n",
    "        s=format(n, \"032b\")\n",
    "        s1=list(s)\n",
    "        s2=''.join(s1[::-1])\n",
    "        return int(s2,2)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # @param n, an integer\n",
    "    # @return an integer\n",
    "    def reverseBits(self, n):\n",
    "        res = 0\n",
    "        for i in range(32):\n",
    "            res = (res << 1) | (n & 1)\n",
    "            n >>= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, n: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(32):\n",
    "            res = (res << 1) | (n & 1)\n",
    "            n = n >> 1\n",
    "        return res\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
